package com.leetcode.study.wechat;

import java.util.*;

public class WeChatSolution001 {
    /**
     * @see <a href="https://mp.weixin.qq.com/s/iqcOm9LutfXDeBIqTRoMMg">https://mp.weixin.qq.com/s/iqcOm9LutfXDeBIqTRoMMg</a>
     * <p>题目描述：
     * <p>现在有 n 位工程师和 6 项工作（编号为 0 至 5），现在给出每个人能够胜任的工作序号表
     * <p>（用一个字符串表示，比如：045，表示某位工程师能胜任 0号，4号，5号 工作）。
     * <p>现在需要进入工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，
     * <p>两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排
     * <p>在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。
     */

    private int backTrack(Vector<String> arr, int count, int index, Map<Character, Integer> tagMap) {
        // 满足条件，输出结果
        if (index == arr.size()) {
            count++;
            return count;
        }
        String str = arr.get(index);
        // 枚举所有可能路径
        for (int i = 0; i < str.length(); i++) {
            if (tagMap.size() == 0 || !tagMap.containsKey(str.charAt(i)) || tagMap.get(str.charAt(i)) == 0) {
                tagMap.put(str.charAt(i), 1);
                count = backTrack(arr, count, index + 1, tagMap);
                tagMap.put(str.charAt(i), 0);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        WeChatSolution001 test001 = new WeChatSolution001();
        int n;
        Scanner in = new Scanner(System.in);
        System.out.print("请输入员工数：");
        n = Integer.parseInt(in.nextLine());
        Vector<String> arr = new Vector<String>();
        String tmp;
        for (int i = 0; i < n; i++) {
            System.out.print("请输入第" + (i + 1) + "为员工可以胜任的工作：");
            tmp = in.nextLine();
            arr.add(tmp);
        }

        int count = 0;
        Map<Character, Integer> tagMap = new HashMap<Character, Integer>();
        count = test001.backTrack(arr, count, 0, tagMap);
        System.out.println("可分配方案：" + count);
    }

}
